|
In the mathematics of infinite graphs, an end of a graph represents, intuitively, a direction in which the graph extends to infinity. Ends may be formalized mathematically as equivalence classes of infinite paths, as havens describing strategies for pursuit-evasion games on the graph, or (in the case of locally finite graphs) as topological ends of topological spaces associated with the graph. Ends of graphs may be used (via Cayley graphs) to define ends of finitely generated groups. Finitely generated infinite groups have one, two, or infinitely many ends, and the Stallings theorem about ends of groups provides a decomposition for groups with more than one end. ==Definition and characterization== Ends of graphs were defined by in terms of equivalence classes of infinite paths.〔However, as point out, ends of graphs were already considered by .〕 A in an infinite graph is a semi-infinite simple path; that is, it is an infinite sequence of vertices ''v''0, ''v''1, ''v''2, ... in which each vertex appears at most once in the sequence and each two consecutive vertices in the sequence are the two endpoints of an edge in the graph. According to Halin's definition, two rays ''r''0 and ''r''1 are equivalent if there is another ray ''r''2 (not necessarily different from either of the first two rays) that contains infinitely many of the vertices in each of ''r''0 and ''r''1. This is an equivalence relation: each ray is equivalent to itself, the definition is symmetric with regard to the ordering of the two rays, and it can be shown to be transitive. Therefore, it partitions the set of all rays into equivalence classes, and Halin defined an end as one of these equivalence classes. An alternative definition of the same equivalence relation has also been used:〔E.g., this is the form of the equivalence relation used by .〕 two rays ''r''0 and ''r''1 are equivalent if there is no finite set ''X'' of vertices that separates infinitely many vertices of ''r''0 from infinitely many vertices of ''r''1. This is equivalent to Halin's definition: if the ray ''r''2 from Halin's definition exists, then any separator must contain infinitely many points of ''r''2 and therefore cannot be finite, and conversely if ''r''2 does not exist then a path that alternates as many times as possible between ''r''0 and ''r''1 must form the desired finite separator. Ends also have a more concrete characterization in terms of havens, functions that describe evasion strategies for pursuit-evasion games on a graph ''G''.〔The haven nomenclature, and the fact that two rays define the same haven if and only if they are equivalent, is due to . proved that every haven comes from an end, completing the bijection between ends and havens, using a different nomenclature in which they called havens "directions".〕 In the game in question, a robber is trying to evade a set of policemen by moving from vertex to vertex along the edges of ''G''. The police have helicopters and therefore do not need to follow the edges; however the robber can see the police coming and can choose where to move next before the helicopters land. A haven is a function β that maps each set ''X'' of police locations to one of the connected components of the subgraph formed by deleting ''X''; a robber can evade the police by moving in each round of the game to a vertex within this component. Havens must satisfy a consistency property (corresponding to the requirement that the robber cannot move through vertices on which police have already landed): if ''X'' is a subset of ''Y'', and both ''X'' and ''Y'' are valid sets of locations for the given set of police, then β(''X'') must be a superset of β(''Y''). A haven has order ''k'' if the collection of police locations for which it provides an escape strategy includes all subsets of fewer than ''k'' vertices in the graph; in particular, it has order ℵ0 if it maps every finite subset ''X'' of vertices to a component of ''G'' \ ''X''. Every ray in ''G'' corresponds to a haven of order ℵ0, namely, the function β that maps every finite set ''X'' to the unique component of ''G'' \ ''X'' that contains infinitely many vertices of the ray. Conversely, every haven of order ℵ0 can be defined in this way by a ray.〔The proof by that every haven can be defined by a ray is nontrivial and involves two cases. If the set (where ''X'' ranges over all finite sets of vertices) is infinite, then there exists a ray that passes through infinitely many vertices of ''S'', which necessarily determines β. On the other hand, if ''S'' is finite, then show that in this case there exists a sequence of finite sets ''X''''i'' that separate the end from all points whose distance from an arbitrarily chosen starting point in ''G'' \ ''S'' is ''i''. In this case, the haven is defined by any ray that is followed by a robber using the haven to escape police who land at set ''X''''i'' in round ''i'' of the pursuit-evasion game.〕 Two rays are equivalent if and only if they define the same haven, so the ends of a graph are in one to one correspondence with its havens of order ℵ0. 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「End (graph theory)」の詳細全文を読む スポンサード リンク
|